package com.kjc.demo.basic.algorithmtest;

public class SearchTest {
	
	public static int insertValue(int[] arr,int left ,int right ,int findValue) {
		
		if(left > right && findValue < arr[left] && findValue > arr[right]) {
			return -1;
		}
		int mid = left + (right-left)*(findValue-arr[left])/(arr[right] - arr[left]);
		int midvalue = arr[mid];
		if(midvalue > findValue) {
			return insertValue(arr,left,mid-1,findValue);
		}else if(midvalue < findValue) {
			return insertValue(arr,mid+1,right,findValue);
		}else {
			return mid;
		}
	}
	
	public static int binarySearch(int[] arr,int findValue) {
		int left = 0;
		int right = arr.length;
		while(left < right) {
			int mid = (left + right) /2;
			if(findValue == arr[mid]) {
				return mid;
			}
			if(findValue < arr[mid]) {
				right = mid - 1;
			}
			if(findValue > arr[mid]) {
				left = mid + 1;
			}
		}
		return -1;
	}
	
	public static int binarySearch(int[] arr,int left ,int right,int findValue) {
		
		int mid = (left + right)/2;
		if(arr[mid] == findValue) {
			return mid;
		}else if(arr[mid] > findValue) {
			return binarySearch(arr,left , mid-1,findValue);
		}else if(arr[mid] < findValue) {
			return binarySearch(arr,mid+1,right,findValue);
		}
		
		return -1;
	}
	
}
